Introduction to Machine Learning

Chapter 11: Imbalanced Data and Oversampling

1. Introduction

When one class makes up 1 % of your data, a model that predicts the majority class every single time scores 99 % accuracy and detects nothing. Chapter 4 addressed half of this problem by replacing accuracy with metrics that cannot be gamed this way. This chapter addresses the other half: changing the data rather than the metric.

We develop the oversampling family in order of sophistication. Random oversampling simply duplicates minority samples, which invites overfitting to the exact duplicated points; adding shrinkage jitters them apart. SMOTE synthesises genuinely new samples by interpolating between minority neighbours. Borderline-SMOTE concentrates that synthesis near the decision boundary, where it actually changes the classifier, and ADASYN goes further by generating more samples where the local neighbourhood is hardest to classify.

Learning Objectives

2. Theory

2.1 OverSampling for Imbalanced Data

Oversampling is a data balancing technique that generates more samples of the minority class to address class imbalance.

Why OverSampling?

In imbalanced datasets, the majority class can dominate the learning process, causing the model to bias towards it. Oversampling helps by:

Popular Oversampling Methods: The four methods listed below are developed in order in the next section, each one addressing a weakness of the one before it.

3. Interactive Examples

Random Oversampling

The simplest strategy to balance imbalance in a dataset is to randomly choose samples of the minority class and repeat or duplicate them, also called random oversampling with replacement.

How it works:

Problem with Random Sampling:

Random oversampling can often lead to overfitting of the model since the generated synthetic observations get repeated, and the model sees the same observations again and again.

Random Oversampling with Shrinkage

The shrinkage parameter in RandomOverSampler lets us perturb or shift each point by a small amount.

Visualization of Random Oversampling with Shrinkage Three-panel illustration showing minority class samples before oversampling, after exact duplication, and after oversampling with shrinkage of 0.2. Random Oversampling with Shrinkage Comparing exact duplication with controlled perturbation of minority samples Before Oversampling Original class distribution FEATURE SPACE Majority class Minority class Without Shrinkage Random oversampling · exact copies FEATURE SPACE ! Risk of overfitting Exact duplicates repeat the same signal. With Shrinkage = 0.2 Random oversampling · slight perturbations FEATURE SPACE Lower overfitting risk Small shifts add useful variation. δ = a slightly shifted version of Δ s*

SMOTE (Synthetic Minority Oversampling Technique)

Shrinkage jitters the duplicated points but still adds no new information. SMOTE takes a different route and avoids duplication altogether, by creating genuinely new samples through interpolation between existing minority samples.

How SMOTE Works:

SMOTE Algorithm

  1. Consider only the samples from the minority class
  2. Train KNN on the minority samples. A typical value of k is 5
  3. For each minority sample, draw a line between the point and each of its KNN examples
  4. For each such line segment, randomly pick a point to create a new synthetic example
  5. If \(x_i\) is the selected point and \(x_{nn}\) is the neighbor, then each axis/dimension of the synthetic point is computed as:
\[ x_{synthetic} = x_i + \lambda \cdot (x_{nn} - x_i) \]

Where \(\lambda\) is a random number between 0 and 1.

SMOTE Algorithm Visualization A selected minority sample P1 is connected to its nearest minority neighbors K1 and K2. A new synthetic minority sample is generated at a point along the line between P1 and a neighbor. SMOTE Algorithm Visualization Synthetic Minority Over-sampling Technique Majority class K1 K2 nearest neighbor nearest neighbor P1 selected minority sample Synthetic sample x_synthetic Legend Majority class Minority neighbor Chosen sample New synthetic sample Neighbor connection Key idea Create a new sample between P1 and a neighbor. i How SMOTE generates a sample A random point is selected along the line from P1 to K1 or K2. This expands the minority class without creating exact duplicates. s*

Problem with SMOTE:

SMOTE spreads the minority class over the region between existing minority samples, and this can increase the overlap between the two classes. The consequences are:

Borderline-SMOTE

The overlap problem arises because plain SMOTE interpolates between all minority samples, including those deep inside the minority region where extra samples change nothing. Borderline-SMOTE is a variation that only generates synthetic samples from minority samples lying near the classification boundary.

Key Idea:

The examples near the classification boundary are more prone to misclassification than those far away from the decision boundary. Producing more such minority samples along the boundary would help the model learn better about the minority class.

Borderline-SMOTE Algorithm

  1. Run a KNN algorithm over the whole dataset (both classes)
  2. Divide the minority class points into three categories:
    1. Noise points: Minority class examples that have all the neighbors from the majority class. These points are buried among majority-class neighbors. They are likely outliers and can safely be ignored as "noise."
    2. Safe points: Have more minority-class neighbors than majority-class neighbors. Such observations don't contain much information and can be safely ignored.
    3. Danger points: Have more majority-class neighbors than minority-class neighbors. This implies that such observations are on or close to the boundary between the two classes.
  3. Train a KNN model only on the minority class examples
  4. Apply the SMOTE algorithm to the Danger points only. Note that the neighbors of these Danger points may or may not be marked as Danger.
Borderline-SMOTE Visualization A two-panel illustration showing original class imbalance and the application of Borderline-SMOTE to a danger sample near the class boundary. Borderline-SMOTE Focusing synthetic sampling where minority observations are most vulnerable a) Original class imbalance Minority samples are concentrated safely inside the region Majority class Minority class (safe) b) Borderline-SMOTE application A danger sample is selected near the decision boundary P1 K1 K2 K3 new synthetic samples Majority Minority neighbor Danger sample Why Borderline-SMOTE? The technique focuses heavily on boundary points, while samples safely inside the minority cluster are not sampled. It strengthens the border between classes rather than adding unnecessary support to the interior. sample the edge s*

Potential Issues with Borderline-SMOTE:

ADASYN (Adaptive Synthetic Sampling)

Borderline-SMOTE treats every borderline sample the same way. ADASYN refines this further by generating more synthetic samples where the local neighborhood is harder to classify, and fewer where it is already easy.

Key Differences from SMOTE:

ADASYN Algorithm

  1. First, train a KNN on the entire dataset (both majority and minority classes)
  2. For each observation of the minority class, find the hardness factor. This factor tells us how difficult it is to classify that data point.
    \[ r = \frac{M}{K} \]
    Where:
    • M = count of majority class neighbors
    • K = total number of nearest neighbors
  3. For each minority observation, generate synthetic samples proportional to the hardness factor by drawing a line between the minority observation and its neighbors (neighbors could be from the majority class or minority class). The harder it is to classify a data point, the more synthetic samples will be created for it.
ADASYN Visualization Comparison of original class imbalance and ADASYN adaptive synthetic sampling, showing more generated samples in a low-density region and fewer in a high-density region. ADASYN Visualization Adaptive synthetic sampling focuses learning where classification is hardest a) Original class imbalance Minority examples are sparse across the feature space FEATURE SPACE Majority class abundant observations P1 · low density harder to classify P2 · high density easier to classify Minority class Only a few minority samples are available. ADASYN uses their local difficulty to guide synthesis. b) ADASYN application Synthetic samples adapt to local classification difficulty FEATURE SPACE P1 · high r more synthetic samples P2 · low r fewer synthetic samples Adaptive generation Sampling intensity follows the hardness factor r. Hard regions receive more support for learning. ADASYN generates more samples for harder-to-classify points It adapts to the local density of each minority sample. s*

4. Numerical Solutions

SMOTE Calculation Example

Let's work through a concrete SMOTE example:

Given:

Calculate the synthetic sample:

\[ x_{synthetic} = x_i + \lambda \cdot (x_{nn} - x_i) \]

For x-coordinate:

\[ x_{synth} = 2 + 0.4 \times (4 - 2) = 2 + 0.4 \times 2 = 2 + 0.8 = 2.8 \]

For y-coordinate:

\[ y_{synth} = 3 + 0.4 \times (5 - 3) = 3 + 0.4 \times 2 = 3 + 0.8 = 3.8 \]

Result: New synthetic sample = (2.8, 3.8)

ADASYN Hardness Factor Calculation

Consider a minority class sample with K=5 nearest neighbors:

Given:

Calculate hardness factor:

\[ r = \frac{M}{K} = \frac{3}{5} = 0.6 \]

Interpretation: This sample has a hardness factor of 0.6, meaning it's relatively difficult to classify because it's surrounded by mostly majority class neighbors. It's likely near the classification boundary. ADASYN will generate more synthetic samples for this point compared to samples with lower hardness factors.

5. Try It Yourself

Problem 1: SMOTE Calculation

Given:

Task: Calculate the coordinates of the new synthetic sample using SMOTE.

Solution:

Using the formula: \(x_{synthetic} = x_i + \lambda \cdot (x_{nn} - x_i)\)

For x-coordinate:

\[ x_{synth} = 1 + 0.25 \times (7 - 1) = 1 + 0.25 \times 6 = 1 + 1.5 = 2.5 \]

For y-coordinate:

\[ y_{synth} = 2 + 0.25 \times (8 - 2) = 2 + 0.25 \times 6 = 2 + 1.5 = 3.5 \]

Result: New synthetic sample = (2.5, 3.5)

Problem 2: ADASYN Hardness Factor

Consider a minority class sample with K=7 nearest neighbors:

Tasks:

  1. Calculate the hardness factor r
  2. Interpret what this hardness factor means
  3. If another sample has hardness factor r=0.2, which sample will have more synthetic samples generated?

Solution:

  1. Hardness factor: \(r = M / K = 5 / 7 \approx 0.714\)
  2. Interpretation: This sample has a high hardness factor (0.714), meaning it's difficult to classify because it's surrounded by mostly majority class neighbors. It's likely near the classification boundary.
  3. Comparison: The sample with r=0.714 will have more synthetic samples generated than the sample with r=0.2. ADASYN generates samples proportional to the hardness factor, so harder-to-classify samples get more attention.
Problem 3: Choosing the Right Oversampling Method

You have an imbalanced dataset with the following characteristics:

Task: Which oversampling method would you choose and why?

Solution:

Recommended method: Borderline-SMOTE

Reasoning:

  • Focus on boundary samples: Since there are minority samples close to the majority class boundary, Borderline-SMOTE will generate synthetic samples specifically in these critical regions.
  • Ignore noise: Borderline-SMOTE identifies and ignores noise points (minority samples surrounded by majority samples), which prevents generating synthetic samples in noisy regions.
  • Balance: It focuses on the "danger" points (near the boundary) while ignoring "safe" points (deep inside minority clusters), which is exactly what this dataset needs.

Alternative: ADASYN could also work well since it adapts to the hardness of each sample, but Borderline-SMOTE is more specifically designed for boundary-focused sampling.

6. Interactive Quiz

Answer all 2 questions. Click an option for instant feedback.

Your score: 0 / 2

7. Key Takeaways

OverSampling Techniques:

8. Common Pitfalls

️ OverSampling: